/**
 * CS560 Wooden Puzzle
 * Winning Configuration Finder
 * 
 * Noriko Cassman 
 * Michael Lee
 * Danny Chhouen
 * Kan Sritong
 * Benjamin Cichy
 * 
 * Due for demo on May 16, 2012
 *
 */

import java.util.*;
import java.io.*;

/**
 * PuzzleSolver class. Finds and solves the wooden puzzle problem given in
 * class.
 */
public class PuzzleSolver {
	private HashSet<Board> configHistory;
	private LinkedList<Board> configHolder;
	private ArrayList<Integer[]> moves;
	private Board goalBoard;
	private Board startBoard;

	/**
	 * Constructor for PuzzleSolver. Initializes the boards for given start and
	 * goal configurations, then tracks the time to solve the puzzle.
	 * 
	 * @param startConfig
	 *            Scanner object that describes the start configuration.
	 * @param goalConfig
	 *            Scanner object that describes the goal configuration.
	 */
	public PuzzleSolver(Scanner startConfig, Scanner goalConfig) {
		configHolder = new LinkedList<Board>();
		configHistory = new HashSet<Board>();
		startBoard = new Board(startConfig);
		goalBoard = new Board(goalConfig);

		long startTime = System.nanoTime();

		try {
			this.solve(startBoard);
		} finally {
			long totalTime = System.nanoTime() - startTime;
			totalTime = totalTime / 1000000;
			System.out.println("Time taken to solve the puzzle: " + totalTime
					+ " milliseconds");
		}
	}

	/**
	 * backTracer returns all of the moves taken to get to the goal
	 * configuration. Uses the parent/child links from the Queue of Boards.
	 * Moves then reversed to be in chronological order.
	 * 
	 * @param thisBoard
	 *            The board being backtracked
	 * @return moves An ArrayList of integers containing all the moves
	 */
	private static ArrayList<Integer[]> backTracer(Board thisBoard) {
		ArrayList<Integer[]> moves = new ArrayList<Integer[]>();
		while (thisBoard != null) {
			if (thisBoard.getMove() != null) {
				moves.add(thisBoard.getMove());
				thisBoard = thisBoard.getParent();
			} else {
				break;
			}
		}
		Collections.reverse(moves);

		return moves;
	}

	/**
	 * printMoves prints the moves taken to get to the goal configuration. Each
	 * puzzle piece has its own letter that corresponds to its index from the
	 * initial configuration.
	 * 
	 * @param moves
	 *            An ArrayList of integers that stores all moves for the
	 *            solution
	 */
	public void printMoves(ArrayList<Integer[]> moves) {

		int counterz = 0;

		for (Iterator<Integer[]> i = moves.iterator(); i.hasNext();) {
			Integer[] blockMoves = i.next();

			// translate each piece's id to it's letter
			if (blockMoves != null) {
				if (blockMoves[4] == 0) {
					System.out.print("Piece A moves ");
				} else if (blockMoves[4] == 1) {
					System.out.print("Piece B moves ");
				} else if (blockMoves[4] == 2) {
					System.out.print("Piece C moves ");
				} else if (blockMoves[4] == 3) {
					System.out.print("Piece D moves ");
				} else if (blockMoves[4] == 4) {
					System.out.print("Piece E moves ");
				} else if (blockMoves[4] == 5) {
					System.out.print("Piece F moves ");
				} else if (blockMoves[4] == 6) {
					System.out.print("Piece G moves ");
				} else if (blockMoves[4] == 7) {
					System.out.print("Piece H moves ");
				} else if (blockMoves[4] == 8) {
					System.out.print("Piece I moves ");
				} else if (blockMoves[4] == 9) {
					System.out.print("Piece J moves ");
				}

				// describes what movement occurred
				if (blockMoves[0] == blockMoves[2]
						&& blockMoves[1] < blockMoves[3]) {
					System.out.println("Right");
				} else if (blockMoves[0] == blockMoves[2]
						&& blockMoves[1] > blockMoves[3]) {
					System.out.println("Left");
				} else if (blockMoves[1] == blockMoves[3]
						&& blockMoves[0] < blockMoves[2]) {
					System.out.println("Down");
				} else if (blockMoves[1] == blockMoves[3]
						&& blockMoves[0] > blockMoves[2]) {
					System.out.println("Up");
				}
			}

			// count the total number of moves taken to solve the puzzle
			counterz++;
		}

		System.out.println("\nSuccess, found the goal!");
		System.out.println("Total move count: " + counterz);
		System.out.println("There are " + configHistory.size()
				+ " configurations in the Config History.");

	}

	/**
	 * Solves the board using a breadth-first strategy (BFS). Finds all next
	 * legal moves possible and puts those configurations into a Queue, then
	 * does the same at each level of next moves. Compares each new
	 * configuration to the History of all configurations to avoid infinite
	 * loops.
	 * 
	 * @param currBoard
	 *            Board to be solved.
	 */
	public void solve(Board currBoard) {
		configHolder.addFirst(currBoard); // put the board into the Queue
		while (!configHolder.isEmpty()) {

			// if this board is the goal board, done! prints the moves taken to
			// get
			// to this board
			if (currBoard.isGoal(goalBoard)) {
				moves = backTracer(currBoard);
				printMoves(moves);
				return;
			}

			// get every possible next legal move for each block, resulting in
			// multiple new Boards
			for (int i = 0; i < currBoard.getBlocks().size(); i++) {
				Board up = currBoard.move(i, 1, 0);
				Board down = currBoard.move(i, -1, 0);
				Board left = currBoard.move(i, 0, -1);
				Board right = currBoard.move(i, 0, 1);

				// Link the new Board in the Queue to its parent, the current
				// Board; add the new Board to the History; add the new Board to
				// the Queue
				if (up != null && !configHistory.contains(up)) {
					up.setParent(currBoard);
					configHistory.add(up);
					configHolder.addFirst(up);
				}
				if (down != null && !configHistory.contains(down)) {
					down.setParent(currBoard);
					configHistory.add(down);
					configHolder.addFirst(down);
				}
				if (left != null && !configHistory.contains(left)) {
					left.setParent(currBoard);
					configHistory.add(left);
					configHolder.addFirst(left);
				}
				if (right != null && !configHistory.contains(right)) {
					right.setParent(currBoard);
					configHistory.add(right);
					configHolder.addFirst(right);
				}

			}

			// using the pollLast method makes LinkedList a Queue and
			// allows for BFS
			currBoard = configHolder.pollLast(); //
		}
		return;
	}

	/**
	 * Getter method.
	 * 
	 * @return moves taken to arrive at the solution.
	 */
	public ArrayList<Integer[]> getMoves() {
		return moves;
	}

	/**
	 * Main method. Reads in two arguments corresponding to the start and goal
	 * configurations and runs PuzzleSolver on them. Throws FileNotFound and
	 * IllegalArgument exceptions.
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		String start;
		String goal;
		Scanner startFile;
		Scanner goalFile;

		if (args.length == 2) {
			start = args[0];
			goal = args[1];

			try {
				startFile = new Scanner(new File(start));
				goalFile = new Scanner(new File(goal));
				PuzzleSolver solver = new PuzzleSolver(startFile, goalFile);
			} catch (FileNotFoundException e) {
				System.out.println("File not found.");
			}

		} else {
			throw new IllegalArgumentException("Invalid number of arguments.");
		}
	}
}